import java.util.Stack;

class Solution {

    public boolean IsPopOrder(int [] pushV,int[] popV) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for(int i=0;i<pushV.length;i++) {
            stack.push(pushV[i]);
            while(j<popV.length && !stack.empty()   //在j不越界，栈不为空的前提下去判断栈顶元素和popV序列元素是否相等
                    && stack.peek()==popV[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
























    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++) {
            char ch=s.charAt(i);
            //左括号入栈
            if(ch=='(' || ch== '[' || ch=='{') {
                stack.push(ch);
            }else {
                //遇到右括号
                if(stack.empty()) {
                    return false;//先遇到了右括号，不匹配，直接返回false
                }else {
                    //栈不为空，取栈顶元素
                    char chL=stack.peek();
                    if(chL=='(' || chL== '[' || chL=='{') {
                        //证明当前这一对括号是匹配的
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }
        return stack.empty();
    }


























    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<tokens.length;i++) {
            String s=tokens[i];
            if(!isOperation(s)) {
                //是数字,push进栈中
                Integer ret=Integer.valueOf(s);
                stack.push(ret);
            }else {
                //是符号
                Integer num2=stack.pop();
                Integer num1=stack.pop();
                switch(s) {
                    case "+" :{
                        stack.push(num1+num2);
                        break;
                    }
                    case "-" :{
                        stack.push(num1-num2);
                        break;
                    }
                    case "*" :{
                        stack.push(num1*num2);
                        break;
                    }
                    case "/" :{
                        stack.push(num1/num2);
                        break;
                    }
                }
            }
        }
        return stack.pop();
    }

    public boolean isOperation(String s) {
        if(s.equals("+") ||s.equals("-") ||s.equals("*") ||s.equals("/")) {
            return true;
        }
        return false;
    }
}